- Рекуррентная формула
-
Рекуррентная формула — формула вида , выражающая каждый член последовательности через p предыдущих членов.
Общая проблематика вычислений с использованием рекуррентных формул является предметом теории рекурсивных функций.
Содержание
Примеры
- Вычисление факториала натурального числа:
- причём
- Вычисление чисел Фибоначчи задаётся формулами:
- Значение интеграла удовлетворяет рекуррентной формуле:
- Решение дифференциального уравнения Бесселя может быть записано в виде степенного ряда:
- Чтобы определить коэффициенты , достаточно установить, что для всех n ⩾ 1. После чего сразу получается известный результат:
- Длина стороны при удвоении числа сторон вписанного правильного многоугольника:
- где R — радиус описанной окружности.
- Существует формула, выражающая общий член линейной рекуррентной последовательности через корни её характеристического многочлена. Например, для последовательности Фибоначчи такой формулой является формула Бине.
Приложения
Рекуррентные формулы используются для описания времени работы алгоритма, рекурсивно обращающегося к самому себе. В такой формуле время, требуемое для решения задачи объемом ввода n, выражается через время решения вспомогательных подзадач.[1]
См. также
Примечания
- ↑ Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн Алгоритмы. Построение и анализ = Introduction To Algorithms / И. Красиков. — Издательский дом "Вильямс", 2005. — С. 79. — 1296 с.
Категории:- Теория алгоритмов
- Алгебра
- Ряды и последовательности
- Рекурсия
- Вычисление факториала натурального числа:
Wikimedia Foundation. 2010.